'''
被shudu.py 、jie_shudu.py引用
求数独的解以及生成数独矩阵
'''
import random


def jie_blank(b_matrix):  # 求解数独函数，求解空白格的坐标以及对应可能的值
    blank_ij = []  # 该列表内容为列表，子列表包含元组(i, j)坐标，以及符合该位置条件的整型数字(a, b, c……)
    for i in range(9):  # 遍历数独
        for j in range(9):
            if b_matrix[i][j] == 0:  # 数独为0时
                t = (i, j)  # 将空白格坐标记录下来
                li = [t]  # 添加到临时列表
                for p in number_list:  # 遍历1-9
                    if check(b_matrix, i, j, p):  # 检查该位置符合条件的数字，将其填入
                        li.append(p)
                blank_ij.append(li)  # 将临时列表填入
    return blank_ij


def jie_matrix(j_matrix):  # 解数独函数，将传入的含零数独解出其答案
    j_matrix_answer = [[col for col in row] for row in j_matrix]  # 先将数独列表复制一份
    blank_ij = jie_blank(j_matrix_answer)  # 获取空白格坐标以及符合条件的数字
    while True:
        p = [len(i) for i in blank_ij]  # 获取空白格列表的子列表长度
        if len(p) == 0:  # 当空白格长度为0时，表明：数独已经解出来了
            break
        elif min(p) == 2:  # 先将数独符合条件数字为1种可能的情况，填入答案中
            index = p.index(2)
            i, j = blank_ij[index][0]  # 获取坐标
            j_matrix_answer[i][j] = blank_ij[index][1]  # 将可能性为1种的情况直接填入答案
            blank_ij = jie_blank(j_matrix_answer)  # 更新空白格列表
        else:
            break
    return j_matrix_answer


# 输出数独矩阵
def print_matrix(matrix):
    print('—' * 19)
    for row in matrix:
        print('|' + ' '.join([str(col) for col in row]) + '|')
    print('—' * 19)


def shuffle_number(num_list):
    random.shuffle(num_list)  # random.shuffle() 函数将序列中的元素随机打乱
    return num_list


def check(matrix, i, j, number):
    if number in matrix[i]:  # 行内是否出现该数字
        return False
    if number in [row[j] for row in matrix]:  # 列内是否出现该数字
        return False
    group_i, group_j = int(i / 3), int(j / 3)
    if number in [matrix[i][j] for i in range(group_i * 3, (group_i + 1) * 3) for j in
                  range(group_j * 3, (group_j + 1) * 3)]:  # 九宫格内是否出现该数字
        return False
    return True


def build_game(matrix, i, j, number):  # 生成数独
    if i > 8 or j > 8:
        return matrix
    if check(matrix, i, j, number):
        b_matrix = [[col for col in row] for row in matrix]  # 先将数独列表复制一份
        b_matrix[i][j] = number  # 数字符合要求，填入列表
        next_i, next_j = (i + 1, 0) if j == 8 else (i, j + 1)  # 获取下一个空
        for num in shuffle_number(number_list):  # 随机获取数字（1-9）；该空总有一个数字可以填进去
            re_matrix = build_game(b_matrix, next_i, next_j, num)
            if re_matrix and sum([sum(row) for row in re_matrix]) == 405:  # 405 == (1+2+……+9)*9 == 数独所有数字之和
                return re_matrix
    return None  # 当运行到这里，说明前面数字不符合条件


# 随机覆盖数独数组中的N个位置
# matrix_all表示整个数独数组
# matrix_blank表示部分被替换为0的用于显示的数组
# blank_ij表示被覆盖位置的i和j
def give_me_a_game(blank_size=9):  # blank_size：空白格的数量
    matrix_all = build_game(matrix, 0, 0, random.choice(number_list))  # matrix_all完整的数独。
    # choice() 方法返回一个（列表，元组或字符串中的）随机项。
    set_ij = set()  # set，集合，元素不重复。用于存放空白格的坐标
    while len(list(set_ij)) < blank_size:
        set_ij.add(
            str(random.choice([0, 1, 2, 3, 4, 5, 6, 7, 8])) + ',' + str(random.choice([0, 1, 2, 3, 4, 5, 6, 7, 8])))
    matrix_blank = [[col for col in row] for row in matrix_all]  # 先将数独复制一份；该列表用于存放设置了空白格（置0）后的数独
    blank_ij = []  # 存放空白格的坐标
    for ij in list(set_ij):
        i, j = int(ij.split(',')[0]), int(ij.split(',')[1])  # 获取坐标
        blank_ij.append((i, j))  # 将坐标添加进数组
        matrix_blank[i][j] = 0  # 将空白格（置0）填入列表
    return matrix_all, matrix_blank, blank_ij


number_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
matrix = [([0] * 9) for i in range(9)]  # 初始化数独列表
if __name__ == "__main__":
    print_matrix(build_game(matrix, 0, 0, random.choice(number_list)))

'''
生成思路简单描述如下：

遍历每个空格，填入目前为止合法的数字；
如果有数字可以填入，则继续向下一个空格；
如果没有数字可以填入，表示之前的数字有问题，则结束递归；
当递归到最后一个格子的下一个时，表示已经生成完毕，返回即可；
这个过程中对1~9这九个数字的遍历数字会经过shuffle处理，保证随机性而不是每次都得到同一个合法的数独数组；
'''
